package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/
 * @create 2025/8/30 20:17
 * @since JDK17
 */

public class Solution29 {
    int[][] dp;
    int dfs(int[] arr, int i, int s) {
        if (i < 0) {
            return Integer.MIN_VALUE / 2;
        }
        if (dp[i][s] != Integer.MIN_VALUE) {
            return dp[i][s];
        }
        int ans;
        if (s == 0) {   // 不删
            ans = arr[i] + Math.max(0, dfs(arr,i - 1, s));
        } else {    // 删
            ans = Math.max(dfs(arr, i - 1, 0), arr[i] + dfs(arr, i - 1, 1));
        }
        return dp[i][s] = ans;
    }

    public int maximumSum(int[] arr) {
        int n = arr.length, ans = Integer.MIN_VALUE;
        dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        for (int i = 0; i < n; i++) {
            ans = Math.max(dfs(arr, i, 0), Math.max(ans, dfs(arr, i, 1)));
        }
        return ans;
    }
}
